package backtracking;

import java.util.*;

public class ContainsDuplicateiii220 {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums.length < 2) {
            return false;
        }

        int slow = 0;
        int fast = 1;
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(nums[slow]);
        while (fast<nums.length){
            if(fast-slow>k){
                treeSet.remove(nums[slow]);
                slow++;
            }
            Integer higher = treeSet.ceiling(nums[fast]);
            if(higher!=null&& (long)(higher)-(long)(nums[fast])<=t){
                return true;
            }
            Integer lower = treeSet.floor(nums[fast]);
            if(lower!=null&&(long)(nums[fast])-(long)(lower)<=t){
                return true;
            }
            treeSet.add(nums[fast++]);
        }
        return false;
    }
}
